package com.zhn;

/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 * 中等
 * 2.6K
 * 相关企业
 * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
 *
 *
 * 示例 1：
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 */

//先找>=target的第一个
//再找>target的第一个
public class SearchRange {
    public int[] searchRange(int[] nums, int target) {
        int l = search(nums, target);
        int r = search(nums, target + 1);
        if(l==nums.length || nums[l] != target)
            return new int[]{-1,-1};
        return new int[] {l, r-1};
    }
    //找>=target的第一个,target + 1就是 >target的第一个
    private int search(int[] nums, int target) {
        // 右边界下标对应的值大于等于目标值，
        // 当数组中不存在大于等于目标值时，假设num.length位置的值大于等于目标值
        int l = 0;
        int r = nums.length;
        while(l < r){
            int mid = (l+r) >> 1;
            if(nums[mid] >= target)
                r = mid;
            else
                l = mid+1;
        }
        // 循环结束的条件是l == r,而且r下标对应的值大于等于目标值
        return l;
    }
}
